package Algorithm.binaryTree;

import java.util.Arrays;
import java.util.Set;

//https://leetcode-cn.com/problems/heaters/
//475. 供暖器
public class Leetcode475_notice_heaters {
    class Solution {
        Set<Integer> set;

        public int findRadius(int[] houses, int[] heaters) {
            Arrays.sort(heaters);
            int max = 0;
            for(int i=0;i<houses.length;i++){
                int l = binarySearch(houses[i], heaters);
                int lVal;
                int rVal;
                if(l==-1){
                    lVal = Integer.MAX_VALUE;
                    rVal = heaters[l+1];
                }else if(l==heaters.length||l==heaters.length-1){
                    lVal = heaters[heaters.length-1];
                    rVal = Integer.MAX_VALUE;
                }else{
                    lVal = heaters[l];
                    rVal = heaters[l+1];
                }

                int dis = Math.min(Math.abs(houses[i]-lVal), Math.abs(houses[i]-rVal));
                max = Math.max(dis, max);
            }
            return max;
        }


//        public int binarySearch(int target, int[] nums){
//            int l=0;
//            int r = nums.length-1;
//
//            while(l<=r){
//                int mid = (l+r)/2;
//                if(nums[mid]==target){
//                    return mid;
//                }else if(nums[mid]>target){
//                    r = r -1;
//                }else{
//                    l = l + 1;
//                }
//            }
//
//            return l-1;
//        }

        /**
         * 这样写要比上面的速度要快
         * @param target
         * @param nums
         * @return
         */
        public int binarySearch(int target, int[] nums){
            int l=0;
            int r = nums.length-1;

            if (nums[l] > target) {
                return -1;
            }

            while(l<r){
                int mid = (r - l + 1) / 2 + l;
                if(nums[mid]==target){
                    return mid;
                }else if(nums[mid]>target){
                    r = mid - 1;
                }else{
                    l = mid;
                }
            }

            return l;
        }

    }
}
